/* Copyright 2001,2002,2003 NAH6 BV
 * All Rights Reserved
 *
 *  $Header: /var/lib/cvs/secphone/ui/bignum/PrimalityTest.cpp,v 1.2 2003/11/21 12:39:24 itsme Exp $
 *
 * Implements Miller-Rabin primality test.
 *
 * Used to verify that our DH prime is still a prime number.
 *
 *
 */

#include "CPhone.h"

#include "debug.h"
#include "bignum.h"

#include "fnaPRNG.h"


#include "PrimalityTest.h"


/* ----------------------------------------------------------------------------- */
// primality test

bool MillerRabinTest(const Number& p, const Number& a);

// nr tests needed to make probability of prime
//    less than  2^-80
//  [ handbook of applied cryptography 4.49 ]
static int nrOfMillerRabinTestsNeeded(int nbits)
{
    if (nbits<100) return 27;
    if (nbits<150) return 18;
    if (nbits<200) return 15;
    if (nbits<250) return 12;
    if (nbits<300) return 9;
    if (nbits<350) return 8;
    if (nbits<400) return 7;
    if (nbits<500) return 6;
    if (nbits<600) return 5;
    if (nbits<800) return 4;
    if (nbits<1300) return 3;
    return 2;
}

bool GetRandomNumber(Number& a, int nbits)
{
    ByteVector random;
    if (!theApp.m_rng->RandomData((nbits+7)/8, random))
        return false;
    if (nbits%8)
    {
        random[0] &= (1 << (nbits%8) ) -1;
    }

    a.FromByteVector(random);

    return true;
}

bool MillerRabinPrimalityTest(const Number& n)
{
    Number a;
    
    if (n == 1)
        return FALSE;

    if (n == 2 || n == 3)
        return TRUE;

    if (!n.getbit(0))
        return FALSE;

    // determine optimal parameters for mr-test
    int nrbits= n.NrOfBitsInNumber();
    int nrtests= nrOfMillerRabinTestsNeeded(nrbits);

    // first test with 'random' nr 2. - this is generally faster than
    // all other random nrs. and eliminates a large nr of values.
    if (!MillerRabinTest(n, Number::FromInteger(2)))
    {
        return FALSE;
    }

    for (int i=0 ; i<nrtests ; ++i)
    {

        //  generate a random number from [2 .. n-2 )
        do {
            if (!GetRandomNumber(a, nrbits))
            {
                debug("ERROR getting random number for miller rabin\n");
                return false; // !!! TODO: this is an error, not a result.
            }
            if (a >= 2 &&  a < n-2)  //  a < n-2
                break;
        } while (1);

        if (!MillerRabinTest(n, a))
        {
            if (i>5)    // note exceptional numbers ( needing a large number of tests )
                debug("not a prime after %d steps\n", i);
            return FALSE;
        }
    }

    return TRUE;
}


// do mr on p with random nr a
static bool MillerRabinTest(const Number& p, const Number& a)
{
    Number n= p;
    n -= 1;
    while (!n.getbit(0))
    {
        n /= 2;

        // if (a^n % p == -1) return TRUE;

        if (a.ModularPower(n, p).ModularCompare(-1, p)==0)
            return TRUE;
    }
    //return (a^n % p == 1);
    if (a.ModularPower(n,p).ModularCompare(1, p)==0)
        return TRUE;

    return FALSE;
}

bool IsPrime(const Number& p)
{
    return MillerRabinPrimalityTest(p);
}
